package course;
/**
 * 打表技巧：对于输入和输出简单的数学规律，不妨用暴力解打印出来找到规律
 */
/**
 * 查找表类，用于演示查找表相关的算法实现
 */
/**
 * 查找表类，用于演示查找算法的实现
 */
public class LookUpTable {
    public static void main(String[] args) {
        for(int i = 1; i <= 100; i++){
            int res = SolutionLookUpTable.consecutiveNumbersSumBruteForce(i);
            int res2 = SolutionLookUpTable.consecutiveNumbersSum(i);
            System.out.println((i) + ": " + (res - 1) + "-------" +res2);

        }
    }
    
}

class SolutionLookUpTable{
    /**买苹果
     * 牛客网 https://www.nowcoder.com/practice/61cfbb2e62104bc8aa3da5d44d38a6ef
     * 小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。
     * 
        输入描述：
        输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果
        输出描述：
        输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1
     */
    static int buyAppleBruteForce(int nums){
        if(nums < 6) return -1;
        int minBags = Integer.MAX_VALUE;
        for(int i = 0; 6 * i <= nums; i++){
            for(int j = 0; 8 * j <= nums; j++){
                if(nums == 6 * i + 8 * j)
                    minBags = Math.min(minBags, i + j);
            }
        }
        return minBags == Integer.MAX_VALUE ? -1 : minBags;
    }
    static int buyAppleCore(int n){
        if(n == 6 || n == 8) return 1;
        if(n == 12 || n == 14 || n== 16) return 2;
        if(n < 18 || n % 2 == 1) return -1;
        return (n - 18) / 8 + 3;
    }

    /**
     * 牛羊轮流吃草谁会赢
     */


    /**
     * 829. 连续整数求和----做不出来
     * 给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。 
     * 1 <= n <= 10^9​​​​​​​
     */
    static int consecutiveNumbersSumBruteForce(int n) {
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int s = 0;
            for(int j = i; j <= n; j++){
                s += j;
                if(s == n){
                    ans++;
                    break;
                } else if(s > n){
                    break;
                }
            }
        }
        return ans;
    }

    /**
     * 根据给定规律计算 f(n)
     * 规律：
     * - 如果 n 是 2 的幂，返回 0
     * - 否则，提取奇数部分 m，分析其质因数结构：
     *   - m = p^k        -> 返回 k
     *   - m = p * q      -> 返回 3
     *   - m = p^2 * q    -> 返回 5
     *   - m = p^4        -> 返回 4
     */
    public static int consecutiveNumbersSum(int n) {
        // 1. 如果是 2 的幂：n > 0 且 (n & (n-1)) == 0
        if (n > 0 && (n & (n - 1)) == 0) {
            return 0;
        }
        
        // 2. 去掉因子 2，得到奇数部分 m
        int m = n;
        while (m % 2 == 0) {
            m /= 2;
        }
        
        if (m == 1) {
            return 0; // 已经是 2 的幂，前面应已处理，但保险
        }
        
        // 3. 分解 m 的质因数
        int temp = m;
        int first_p = 0;       // 第一个质因子（实际未使用）
        int first_exp = 0;     // 第一个质因子的指数
        int second_p = 0;      // 第二个质因子（未使用）
        int second_exp = 0;    // 第二个质因子的指数
        int factor_count = 0;  // 质因子种类数
        
        // 先试因子 3, 5, 7, ... 直到 sqrt(temp)
        int p = 3;
        while (p * p <= temp) {
            if (temp % p == 0) {
                int count = 0;
                while (temp % p == 0) {
                    count++;
                    temp /= p;
                }
                if (factor_count == 0) {
                    first_exp = count;
                } else if (factor_count == 1) {
                    second_exp = count;
                }
                factor_count++;
            }
            p += 2;
        }
        
        // 如果 temp > 1，说明还有一个质因子
        if (temp > 1) {
            if (factor_count == 0) {
                first_exp = 1;
            } else if (factor_count == 1) {
                second_exp = 1;
            }
            factor_count++;
        }
        
        // 4. 根据质因数情况返回结果
        if (factor_count == 1) {
            return first_exp;
        } else if (factor_count == 2) {
            if ((first_exp == 2 && second_exp == 1) || (first_exp == 1 && second_exp == 2)) {
                return 5;
            } else {
                return 3;
            }
        } else {
            return 3; // 三个或以上质因子
        }
    }


}